1. Field of the Invention
The present invention relates to a pseudo-random number generator which employs a linear feedback shift register (hereinafter abbreviated as “LFSR”) to generate pseudo-random numbers.
2. Description of the Related Art
While random numbers have been conventionally used for cryptographic algorithms and the like, pseudo-random numbers, which can be generated more easily than true random numbers, tend to be more frequently used because they can be readily handled and processed.
A pseudo-random number generator for generating pseudo-random numbers typically employs LFSR to generate random numbers having a long cycle. The LFSR comprises a plurality of registers connected in series, and an exclusive OR logic circuit (hereinafter called the “XOR circuit”), wherein output data of predetermined registers are fed back to the first one of the registers through the XOR circuit. With the XOR circuit provided in a feedback path, the LFSR delivers random numbers having a relatively long cycle.
For example, LFSR comprised of n registers produces random numbers, the cycle of which is an n-th order linear maximum cycle series (called “M-series”) 2n−1. It should be noted that random numbers provided by the LFSR are repeatedly generated random numbers of the M-series, and the cycle of the LFSR does not refer to a time period, but to the length of the M-series.
In a cryptographic circuit for generating a cryptogram using pseudo-random numbers, and the like, if pseudo-random number series or pseudo-random number generation logic is revealed, an original plaintext can be restored from an acquired cryptogram, thus making it important to efficiently generate unpredictable random number series.
While pseudo-random number series or pseudo-random number generation logic is more difficult to be broken as the order number n of LFSR (the number of registers) is larger for the number of bits of random numbers generated thereby, only LFSR having a small number of bits can be used in some cases due to such constraints as a circuit scale. To address this situation, a variety of techniques have been studied for improving the randomness of pseudo-random numbers generated by lower-order LFSR, and Japanese Patent No. 2937919, for example, describes a pseudo-random number generator which comprises a plurality of clocks at different frequencies, and switches an operation clock (shift clock) supplied to each of registers in LFSR using a predetermined output of the LFSR.
When a shift clock is fixed, the LFSR repeatedly generates the same random number series at a predetermined cycle from a predetermined initial value (SEED). On the other hand, the pseudo-random number generator described in Japanese Patent No. 2937919 cited above switches shift clocks using a predetermined output of the LFSR to cause variations in timing of a shifting operation, with the result that an apparent cycle becomes longer than the cycle determined by the order number of the LFSR.
However, while the foregoing configuration relies on variations in the shifting operation to vary the timing at which a random number is generated, SEED and random number series generated thereby are equal to those which are generated with a fixed shift clock. Specifically, as illustrated in FIG. 1, while random numbers are generated at random time intervals (note, however, that they are continuously generated (dispersed) at constant intervals, when viewed in a certain short duration), they will not disturb the order of random numbers which are generated with a fixed shift clock. Thus, while the pseudo-random number generator described in Japanese Patent No. 2937919 simply improves the randomness over the configuration with a fixed shift clock, it still fails to provide a sufficiently high randomness because of its ever high susceptibility to identification of the pseudo-random number series or the pseudo-random number generation logic.